Copy List with Random Pointer || Clone Graph

Copy List with Random Pointer

Question

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Analysis

LeetCode DIscussion

• 将整个链表复制一遍，复制节点紧跟原节点
• 复制每个节点的random指针，复制节点的random指针同理指向复制节点
• 提取复制后的链表
  • 复制过程需要两个指针，copy与copyiter，copy指向当前需要加入复制链表的节点，copyiter用来连接整个链表（移动的指针）
  • 加入空表头，方便返回结果 copyiter=pseudo_head

Code

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        //Copy the whole list
         RandomListNode iter=head,next;
         
         while(iter!=null){
             next=iter.next;
             RandomListNode copy=new RandomListNode(iter.label);
             iter.next=copy;
             copy.next=next;
             iter=next;
         }
         
         //Copy the random node
         iter=head;
         
         while(iter!=null){
             if(iter.random!=null){
                 iter.next.random=iter.random.next;
             }
             iter=iter.next.next;
         }
         
         //Get the result
         RandomListNode res=new RandomListNode(0);
         RandomListNode copy,copyiter=res;
         iter=head;
         while(iter!=null){
             next=iter.next.next;
             
             copy=iter.next;
             copyiter.next=copy;
             copyiter=copy;
             
             iter.next=next;
             iter=next;
         }
         return res.next;
    }
}

Clone Graph

Question

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Analysis

利用BFS递归对图进行复制，map保存节点val与相应节点的映射关系

Code

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    HashMap<Integer,UndirectedGraphNode> map=new HashMap<Integer,UndirectedGraphNode>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        return clonehelper(node);
    }
    
    private UndirectedGraphNode clonehelper(UndirectedGraphNode node){
        if(node==null)  return null;
        
        if(map.containsKey(node.label)){
            return map.get(node.label);
        }
        
        UndirectedGraphNode copy=new UndirectedGraphNode(node.label);
        map.put(copy.label,copy);
        List<UndirectedGraphNode> neighbor=node.neighbors;
        for(UndirectedGraphNode each:neighbor){
                copy.neighbors.add(clonehelper(each));
        }
        
        return copy;
    }
}